package Search;

import java.util.Arrays;

public class FibonacciSearch {

  public static int maxSize = 20;

  public static void main(String[] args) {
    int[] arr = new int[]{1,8,10,89,1000,1234};
    System.out.println(Arrays.toString(getFib()));
    int index = fibonacciSearch(arr, 89);
    System.out.println("下标为:" + index);

  }

  public static int fibonacciSearch(int[] arr,int key){
    int low = 0;
    int high = arr.length - 1;
    int k = 0;//表示斐波那契分割数值的下标
    int mid = 0;//存放mid值
    int f[]= getFib();//获取到斐波那契数列
    // /获取到斐波那契分割数值的下标
    while(high > f[k] - 1) {
      k++;
    }
    System.out.println("k=" + k);
    //因为f[k]值可能太于arr 的长度，因此我们需要使用Arrays类，构造一个新的数组，并指向arr
    int[]temp = Arrays.copyOf(arr,f[k]);
    //实际上需求使用arr数组最后的数填充temp
    // 举例:
    //temp = {1,8，10，89，1000，1234，0， 0， 0] =>{1,8，10，89，1000，1234,1234,1234,1234}
    for(int i = high + 1; i < temp.length; i++){
      temp[i] = arr[high];
    }
    //使用while来备环处理，找到我们的数key
    while(low <= high) {//只要这个条件满足,就可以找
      mid = low + f[k - 1] - 1;
      System.out.println("mid=" + mid);
      if (key < temp[mid]){
        high = mid - 1;
        //1.全部元素=前面的元素＋后边元素/
        //2.f[k] = f[k-1] +f[k-2]
        //因为前面有f[ k-1]个元素,所以可以继续拆分f[k-1] = f[k-2] + f[k-3]
        //即在f[k-1]的前面继续查找k--
        //即下次备环mid = low + f[k-1-1]-1
        k--;
      }else if (key > temp[mid]){
        low = mid + 1;
        //1.全部元素=前面的元素＋后边元素
        //2.f[k] = f[k-1] + f[k-2]
        //3.因为后面我们有f[k-2]所以可以继续拆分f[k-1] = f[k-3]+f[k-4]
        //4.即在f[k-2]的前面进行查找k -=2
        //5.即下次循环mid = low + f[k - 1 -2] - i
        k = k - 2;
      }else {
        if (mid <= high){
          return mid;
        }return high;
      }
    }
      return -1;
  }

//  得到fibonacci数列的算法
  public static int[] getFib(){
    int[] fib = new int[maxSize];
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < maxSize; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib;
  }
}
